home *** CD-ROM | disk | FTP | other *** search
/ Aminet 49 / Aminet 49 (2002)(GTI - Schatztruhe)[!][Jun 2002].iso / Aminet / util / libs / ttrender.lha / ttrender-2.0 / Developer / source / base / fttrigon.c < prev   
Encoding:
C/C++ Source or Header  |  2002-04-06  |  9.1 KB  |  451 lines
  1. /***************************************************************************/
  2. /*                                                                         */
  3. /*  fttrigon.c                                                             */
  4. /*                                                                         */
  5. /*    FreeType trigonometric functions (body).                             */
  6. /*                                                                         */
  7. /*  Copyright 2001 by                                                      */
  8. /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  9. /*                                                                         */
  10. /*  This file is part of the FreeType project, and may only be used,       */
  11. /*  modified, and distributed under the terms of the FreeType project      */
  12. /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  13. /*  this file you indicate that you have read the license and              */
  14. /*  understand and accept it fully.                                        */
  15. /*                                                                         */
  16. /***************************************************************************/
  17.  
  18.  
  19. #include <ft2build.h>
  20. #include FT_TRIGONOMETRY_H
  21.  
  22.  
  23.   /* the following is 0.2715717684432231 * 2^30 */
  24. #define FT_TRIG_COSCALE  0x11616E8EUL
  25.  
  26.   /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
  27. #define FT_TRIG_MAX_ITERS  23
  28.  
  29.   static const FT_Fixed
  30.   ft_trig_arctan_table[24] =
  31.   {
  32.     4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L,
  33.     58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
  34.     57L, 29L, 14L, 7L, 4L, 2L, 1L
  35.   };
  36.  
  37.   /* the Cordic shrink factor, multiplied by 2^32 */
  38. #define FT_TRIG_SCALE    1166391785UL  /* 0x4585BA38UL */
  39.  
  40.  
  41. #ifdef FT_CONFIG_HAS_INT64
  42.  
  43.   /* multiply a given value by the CORDIC shrink factor */
  44.   static FT_Fixed
  45.   ft_trig_downscale( FT_Fixed  val )
  46.   {
  47.     FT_Fixed  s;
  48.     FT_Int64  v;
  49.  
  50.  
  51.     s   = val;
  52.     val = ( val >= 0 ) ? val : -val;
  53.  
  54.     v   = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL;
  55.     val = (FT_Fixed)( v >> 32 );
  56.  
  57.     return ( s >= 0 ) ? val : -val;
  58.   }
  59.  
  60. #else /* !FT_CONFIG_HAS_INT64 */
  61.  
  62.   /* multiply a given value by the CORDIC shrink factor */
  63.   static FT_Fixed
  64.   ft_trig_downscale( FT_Fixed  val )
  65.   {
  66.     FT_Fixed   s;
  67.     FT_UInt32  v1, v2, k1, k2, hi, lo1, lo2, lo3;
  68.  
  69.  
  70.     s   = val;
  71.     val = ( val >= 0 ) ? val : -val;
  72.  
  73.     v1 = (FT_UInt32)val >> 16;
  74.     v2 = (FT_UInt32)val & 0xFFFF;
  75.  
  76.     k1 = FT_TRIG_SCALE >> 16;       /* constant */
  77.     k2 = FT_TRIG_SCALE & 0xFFFF;    /* constant */
  78.  
  79.     hi   = k1 * v1;
  80.     lo1  = k1 * v2 + k2 * v1;       /* can't overflow */
  81.  
  82.     lo2  = ( k2 * v2 ) >> 16;
  83.     lo3  = ( lo1 >= lo2 ) ? lo1 : lo2;
  84.     lo1 += lo2;
  85.  
  86.     hi  += lo1 >> 16;
  87.     if ( lo1 < lo3 )
  88.       hi += 0x10000UL;
  89.  
  90.     val  = (FT_Fixed)hi;
  91.  
  92.     return ( s >= 0 ) ? val : -val;
  93.   }
  94.  
  95. #endif /* !FT_CONFIG_HAS_INT64 */
  96.  
  97.  
  98.   static FT_Int
  99.   ft_trig_prenorm( FT_Vector*  vec )
  100.   {
  101.     FT_Fixed  x, y, z;
  102.     FT_Int    shift;
  103.  
  104.  
  105.     x = vec->x;
  106.     y = vec->y;
  107.  
  108.     z     = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
  109.     shift = 0;
  110.  
  111.     if ( z < ( 1L << 27 ) )
  112.     {
  113.       do
  114.       {
  115.         shift++;
  116.         z <<= 1;
  117.       } while ( z < ( 1L << 27 ) );
  118.  
  119.       vec->x = x << shift;
  120.       vec->y = y << shift;
  121.     }
  122.     else if ( z > ( 1L << 28 ) )
  123.     {
  124.       do
  125.       {
  126.         shift++;
  127.         z >>= 1;
  128.       } while ( z > ( 1L << 28 ) );
  129.  
  130.       vec->x = x >> shift;
  131.       vec->y = y >> shift;
  132.       shift  = -shift;
  133.     }
  134.     return shift;
  135.   }
  136.  
  137.  
  138.   static void
  139.   ft_trig_pseudo_rotate( FT_Vector*  vec,
  140.                          FT_Angle    theta )
  141.   {
  142.     FT_Int           i;
  143.     FT_Fixed         x, y, xtemp;
  144.     const FT_Fixed  *arctanptr;
  145.  
  146.  
  147.     x = vec->x;
  148.     y = vec->y;
  149.  
  150.     /* Get angle between -90 and 90 degrees */
  151.     while ( theta <= -FT_ANGLE_PI2 )
  152.     {
  153.       x = -x;
  154.       y = -y;
  155.       theta += FT_ANGLE_PI;
  156.     }
  157.  
  158.     while ( theta > FT_ANGLE_PI2 )
  159.     {
  160.       x = -x;
  161.       y = -y;
  162.       theta -= FT_ANGLE_PI;
  163.     }
  164.  
  165.     /* Initial pseudorotation, with left shift */
  166.     arctanptr = ft_trig_arctan_table;
  167.  
  168.     if ( theta < 0 )
  169.     {
  170.       xtemp  = x + ( y << 1 );
  171.       y      = y - ( x << 1 );
  172.       x      = xtemp;
  173.       theta += *arctanptr++;
  174.     }
  175.     else
  176.     {
  177.       xtemp  = x - ( y << 1 );
  178.       y      = y + ( x << 1 );
  179.       x      = xtemp;
  180.       theta -= *arctanptr++;
  181.     }
  182.  
  183.     /* Subsequent pseudorotations, with right shifts */
  184.     i = 0;
  185.     do
  186.     {
  187.       if ( theta < 0 )
  188.       {
  189.         xtemp  = x + ( y >> i );
  190.         y      = y - ( x >> i );
  191.         x      = xtemp;
  192.         theta += *arctanptr++;
  193.       }
  194.       else
  195.       {
  196.         xtemp  = x - ( y >> i );
  197.         y      = y + ( x >> i );
  198.         x      = xtemp;
  199.         theta -= *arctanptr++;
  200.       }
  201.     } while ( ++i < FT_TRIG_MAX_ITERS );
  202.  
  203.     vec->x = x;
  204.     vec->y = y;
  205.   }
  206.  
  207.  
  208.   static void
  209.   ft_trig_pseudo_polarize( FT_Vector*  vec )
  210.   {
  211.     FT_Fixed         theta;
  212.     FT_Fixed         yi, i;
  213.     FT_Fixed         x, y;
  214.     const FT_Fixed  *arctanptr;
  215.  
  216.  
  217.     x = vec->x;
  218.     y = vec->y;
  219.  
  220.     /* Get the vector into the right half plane */
  221.     theta = 0;
  222.     if ( x < 0 )
  223.     {
  224.       x = -x;
  225.       y = -y;
  226.       theta = 2 * FT_ANGLE_PI2;
  227.     }
  228.  
  229.     if ( y > 0 )
  230.       theta = - theta;
  231.  
  232.     arctanptr = ft_trig_arctan_table;
  233.  
  234.     if ( y < 0 )
  235.     {
  236.       /* Rotate positive */
  237.       yi     = y + ( x << 1 );
  238.       x      = x - ( y << 1 );
  239.       y      = yi;
  240.       theta -= *arctanptr++;  /* Subtract angle */
  241.     }
  242.     else
  243.     {
  244.       /* Rotate negative */
  245.       yi     = y - ( x << 1 );
  246.       x      = x + ( y << 1 );
  247.       y      = yi;
  248.       theta += *arctanptr++;  /* Add angle */
  249.     }
  250.  
  251.     i = 0;
  252.     do
  253.     {
  254.       if ( y < 0 )
  255.       {
  256.         /* Rotate positive */
  257.         yi     = y + ( x >> i );
  258.         x      = x - ( y >> i );
  259.         y      = yi;
  260.         theta -= *arctanptr++;
  261.       }
  262.       else
  263.       {
  264.         /* Rotate negative */
  265.         yi     = y - ( x >> i );
  266.         x      = x + ( y >> i );
  267.         y      = yi;
  268.         theta += *arctanptr++;
  269.       }
  270.     } while ( ++i < FT_TRIG_MAX_ITERS );
  271.  
  272.     /* round theta */
  273.     if ( theta >= 0 )
  274.       theta = ( theta + 16 ) & -32;
  275.     else
  276.       theta = - (( -theta + 16 ) & -32);
  277.  
  278.     vec->x = x;
  279.     vec->y = theta;
  280.   }
  281.  
  282.  
  283.   /* documentation is in fttrigon.h */
  284.  
  285.   FT_EXPORT_DEF( FT_Fixed )
  286.   FT_Cos( FT_Angle  angle )
  287.   {
  288.     FT_Vector  v;
  289.  
  290.  
  291.     v.x = FT_TRIG_COSCALE >> 2;
  292.     v.y = 0;
  293.     ft_trig_pseudo_rotate( &v, angle );
  294.  
  295.     return v.x / ( 1 << 12 );
  296.   }
  297.  
  298.  
  299.   /* documentation is in fttrigon.h */
  300.  
  301.   FT_EXPORT_DEF( FT_Fixed )
  302.   FT_Sin( FT_Angle  angle )
  303.   {
  304.     return FT_Cos( FT_ANGLE_PI2 - angle );
  305.   }
  306.  
  307.  
  308.   /* documentation is in fttrigon.h */
  309.  
  310.   FT_EXPORT_DEF( FT_Fixed )
  311.   FT_Tan( FT_Angle  angle )
  312.   {
  313.     FT_Vector  v;
  314.  
  315.  
  316.     v.x = FT_TRIG_COSCALE >> 2;
  317.     v.y = 0;
  318.     ft_trig_pseudo_rotate( &v, angle );
  319.  
  320.     return FT_DivFix( v.y, v.x );
  321.   }
  322.  
  323.  
  324.   /* documentation is in fttrigon.h */
  325.  
  326.   FT_EXPORT_DEF( FT_Angle )
  327.   FT_Atan2( FT_Fixed  dx,
  328.             FT_Fixed  dy )
  329.   {
  330.     FT_Vector  v;
  331.  
  332.  
  333.     if ( dx == 0 && dy == 0 )
  334.       return 0;
  335.  
  336.     v.x = dx;
  337.     v.y = dy;
  338.     ft_trig_prenorm( &v );
  339.     ft_trig_pseudo_polarize( &v );
  340.  
  341.     return v.y;
  342.   }
  343.  
  344.  
  345.   /* documentation is in fttrigon.h */
  346.  
  347.   FT_EXPORT_DEF( void )
  348.   FT_Vector_Unit( FT_Vector*  vec,
  349.                   FT_Angle    angle )
  350.   {
  351.     vec->x = FT_TRIG_COSCALE >> 2;
  352.     vec->y = 0;
  353.     ft_trig_pseudo_rotate( vec, angle );
  354.     vec->x >>= 12;
  355.     vec->y >>= 12;
  356.   }
  357.  
  358.  
  359.   /* documentation is in fttrigon.h */
  360.  
  361.   FT_EXPORT_DEF( void )
  362.   FT_Vector_Rotate( FT_Vector*  vec,
  363.                     FT_Angle    angle )
  364.   {
  365.     FT_Int     shift;
  366.     FT_Vector  v;
  367.  
  368.  
  369.     v.x   = vec->x;
  370.     v.y   = vec->y;
  371.  
  372.     if ( angle && ( v.x != 0 || v.y != 0 ) )
  373.     {
  374.       shift = ft_trig_prenorm( &v );
  375.       ft_trig_pseudo_rotate( &v, angle );
  376.       v.x = ft_trig_downscale( v.x );
  377.       v.y = ft_trig_downscale( v.y );
  378.  
  379.       if ( shift >= 0 )
  380.       {
  381.         vec->x = v.x >> shift;
  382.         vec->y = v.y >> shift;
  383.       }
  384.       else
  385.       {
  386.         shift  = -shift;
  387.         vec->x = v.x << shift;
  388.         vec->y = v.y << shift;
  389.       }
  390.     }
  391.   }
  392.  
  393.  
  394.   /* documentation is in fttrigon.h */
  395.  
  396.   FT_EXPORT_DEF( FT_Fixed )
  397.   FT_Vector_Length( FT_Vector*  vec )
  398.   {
  399.     FT_Int     shift;
  400.     FT_Vector  v;
  401.  
  402.  
  403.     v = *vec;
  404.  
  405.     /* handle trivial cases */
  406.     if ( v.x == 0 )
  407.     {
  408.       return ( v.y >= 0 ) ? v.y : -v.y;
  409.     }
  410.     else if ( v.y == 0 )
  411.     {
  412.       return ( v.x >= 0 ) ? v.x : -v.x;
  413.     }
  414.  
  415.     /* general case */
  416.     shift = ft_trig_prenorm( &v );
  417.     ft_trig_pseudo_polarize( &v );
  418.  
  419.     v.x = ft_trig_downscale( v.x );
  420.     return ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
  421.   }
  422.  
  423.  
  424.   /* documentation is in fttrigon.h */
  425.  
  426.   FT_EXPORT_DEF( void )
  427.   FT_Vector_Polarize( FT_Vector*  vec,
  428.                       FT_Fixed   *length,
  429.                       FT_Angle   *angle )
  430.   {
  431.     FT_Int     shift;
  432.     FT_Vector  v;
  433.  
  434.  
  435.     v = *vec;
  436.  
  437.     if ( v.x == 0 && v.y == 0 )
  438.       return;
  439.  
  440.     shift = ft_trig_prenorm( &v );
  441.     ft_trig_pseudo_polarize( &v );
  442.  
  443.     v.x = ft_trig_downscale( v.x );
  444.  
  445.     *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
  446.     *angle  = v.y;
  447.   }
  448.  
  449.  
  450. /* END */
  451.